package com.myworld.datastructure.tree;

import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

public class BinaryTree<T> {
    /**
     * 根节点
     */
    private  Node<T> root;

    static class Node<T> {
        T root;
        Node left, right, parent;

        public Node(T key) {
            this.root = key;
        }
    }

    public BinaryTree(){

    }
    public BinaryTree(T t){
        this.root=new Node<>(t);
    }

    public Node getRoot(){
        return root;
    }

    /**
     * 先序遍历
     * @param node
     */
    public void preorderTraversal(Node node){
        if(node==null) return;
        Stack<Node> stack=new Stack();
        while (node!=null|| !stack.isEmpty()){
            while(node!=null){
                System.out.println(node.root);
                stack.push(node);
                node=node.left;
            }
            if(!stack.isEmpty()){
                node=stack.pop();
                node=node.right;
            }
        }
    }

    /**
     * 中序遍历
     * @param node
     */
    public void inorderTraversal(Node node){
        if(node==null) return;
        Stack<Node> stack=new Stack();
        while (node!=null|| !stack.isEmpty()){
            while(node!=null){
                stack.push(node);
                node=node.left;
            }
            if(!stack.isEmpty()){
                node=stack.pop();
                System.out.println(node.root);
                node=node.right;
            }
        }
    }

    /**
     * 后序遍历
     * @param node
     */
    public void postorderTraversal(Node node){
        if(node==null) return;
        Stack<Node> stack=new Stack();
        Node lastNode=null;
        while (node!=null|| !stack.isEmpty()){
            while(node!=null){
                stack.push(node);
                node=node.left;
            }
            if(!stack.isEmpty()){
                Node t=stack.pop();
                if(t.right==null||t.right==lastNode){
                   System.out.println(t.root);
                   lastNode=t;
                }else {
                    stack.push(node);
                    node = node.right;
                }
            }
        }
    }

    /**
     * 层序遍历:队列实现
     *     先将结点入队
     *     结点出队：
     *        访问跟结点，在将左，右结点入队
     */
    public void sequenceTraversal(Node node){
        if(node==null) return;
        Queue<Node> queue=new LinkedBlockingQueue<Node>();
        queue.add(node);
        while(queue.isEmpty()){
            node=queue.poll();
            System.out.println(node.root);
            if(node.left!=null) queue.add(node.left);
            if(node.right!=null) queue.add(node.right);
        }

    }

}











